/**
 * @param {number} n
 * @return {number}
 * @description 递归
 */

var fib = function (n) {
    return dp(n)
    function dp(n) {
        if (n === 0) {
            return 0
        }
        if (n === 1) {
            return 1
        }
        let a = 1, b = 0
        for (let i = 1; i < n; i++) {
            a = a + b
            b = a - b
            a %= 1000000007
        }
        return a
    }
};